package org.example.doubleFinger;


import org.example.link_list.ListNode;

public class Intersection_of_linked_lists {
    public static void main(String[] args) {
        //链表相交

        //给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。
        ListNode listNode2 = new ListNode(5);
        listNode2.next = null;
        ListNode listNode3 = new ListNode(4,listNode2);
        ListNode listNode4 = new ListNode(3,listNode3);
        ListNode listNode5 = new ListNode(2,listNode4);
        ListNode headA = new ListNode(1,listNode5);

        ListNode listNode41 = new ListNode(31,listNode3);
        ListNode listNode51 = new ListNode(21,listNode41);
        ListNode headB = new ListNode(11,listNode51);
        ListNode intersectionNode = getIntersectionNode(headA, null);
        System.out.println(intersectionNode);
    }
    public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        int lenA = 0;
        int lenB = 0;
        //计算headA的长度
        ListNode a = headA;
        while (a!=null){
            lenA++;
            a = a.next;
        }
        //计算headB的长度
        ListNode b = headB;
        while (b!=null){
            lenB++;
            b = b.next;
        }
        if(lenB>lenA){
            //将headA和headB交换
            a = headA;
            headA = headB;
            headB = a;
            //将lenA和lenB交换位置
            int c = lenA;
            lenA = lenB;
            lenB  = c;
        }
        //循环一一对比
        while(headA!=null){
            if ((lenA-lenB)>0){
                headA = headA.next;
                lenA--;
            }else {
                if (headA==headB){
                    return headA;
                }
                headA = headA.next;
                headB = headB.next;
            }
        }
        return null;
    }
}
